package ru.eas.sort;

import java.util.Scanner;

public class HeapSort {

    public static void main(String[] args) {
        String testString = "5\n" +
                "2 3 9 2 9";
        Scanner scanner = new Scanner(testString);

//        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }
        HeapSort heapSort = new HeapSort();
        heapSort.sort(array);
        for (int i = 0; i < n; i++) {
            System.out.print(array[i]);
            System.out.print(" ");
        }
    }

    private void sort(int[] array) {
        buildMaxHeap(array);
        int size = array.length;
        for (int i = array.length - 1; i >= 1; i--) {
            swap(array, i, 0);
            siftDown(array, --size, 0);
        }
    }

    private void siftDown(int[] array, int arrayLength, int index) {
        int leftIndex = left(index);
        int rightIndex = right(index);
        int leftValue;
        int rightValue;

        if (leftIndex < arrayLength) {
            leftValue = array[leftIndex];
        } else {
            leftValue = Integer.MIN_VALUE;
        }

        if (rightIndex < arrayLength) {
            rightValue = array[rightIndex];
        } else {
            rightValue = Integer.MIN_VALUE;
        }

        int resultIndex;
        int resultValue;

        if (leftValue > rightValue) {
            resultIndex = leftIndex;
            resultValue = leftValue;
        } else {
            resultIndex = rightIndex;
            resultValue = rightValue;
        }

        if (array[index] >= resultValue) {
            return;
        }

        swap(array, index, resultIndex);
        siftDown(array, arrayLength, resultIndex);
    }

    private void swap(int[] array, int index1, int index2) {
        int value1 = array[index1];
        int value2 = array[index2];
        array[index1] = value2;
        array[index2] = value1;
    }

    private void buildMaxHeap(int[] array) {
        int length = array.length / 2 - 1;
        for (int i = length; i >= 0 ; i--) {
            siftDown(array, array.length, i);
        }
    }

    private int left(int index) {
        return 2 * (index + 1) - 1;
    }

    private int right(int index) {
        return 2 * (index + 1) ;
    }
}
